import heapq

#def merge(*subsequences):
def mergeList(sortKey,*subsequences):
    # prepare a priority queue whose items are pairs of the form
    # (current-value, iterator), one each per (non-empty) subsequence
    heap = [  ]
    intJudge = {0:str,1:int}
    for subseq in subsequences[0]:
        iterator = iter(subseq)
        for current_value_str in iterator:
            current_value_tmp = current_value_str.strip().split('\t')
            current_value = map(lambda x: intJudge[current_value_tmp[x].isdigit()](current_value_tmp[x]), sortKey)
            current_value.append(current_value_str)
            #current_value = intJudge[current_value.isdigit()](current_value)

            # subseq is not empty, therefore add this subseq's pair
            # (current-value, iterator) to the list
            heap.append((current_value, iterator))
            break
    # make the priority queue into a heap
    heapq.heapify(heap)
    while heap:
        # get and yield lowest current value (and corresponding iterator)
        current_value, iterator = heap[0]
        yield current_value[-1].strip()
        for current_value_str in iterator:
            current_value_tmp = current_value_str.strip().split('\t')
            try:
                current_value = map(lambda x: intJudge[current_value_tmp[x].isdigit()](current_value_tmp[x]), sortKey)
                current_value.append(current_value_str)
            except IndexError:
                print ':%s:' % current_value
                exit()


            # subseq is not finished, therefore add this subseq's pair
            # (current-value, iterator) back into the priority queue
            #print heap
            heapq.heapreplace(heap, (current_value, iterator))
            #print heap
            break
        else:
            # subseq has been exhausted, therefore remove it from the queue
            heapq.heappop(heap)

def merge(sortKey,*subsequences):
    # prepare a priority queue whose items are pairs of the form
    # (current-value, iterator), one each per (non-empty) subsequence
    # length of sortKey , must be one
    heap = [  ]
    intJudge = {0:str,1:int}
    for subseq in subsequences[0]:
        iterator = iter(subseq)
        for current_value in iterator:
            current_value = current_value.strip().split('\t')[sortKey[0]]
            current_value = intJudge[current_value.isdigit()](current_value)
            # subseq is not empty, therefore add this subseq's pair
            # (current-value, iterator) to the list
            heap.append((current_value, iterator))
            break
    # make the priority queue into a heap
    heapq.heapify(heap)
    while heap:
        # get and yield lowest current value (and corresponding iterator)
        current_value, iterator = heap[0]
        yield current_value
        for current_value in iterator:
            current_value = current_value.strip().split('\t')[0]
            current_value = intJudge[current_value.isdigit()](current_value)
            # subseq is not finished, therefore add this subseq's pair
            # (current-value, iterator) back into the priority queue
            #print heap
            heapq.heapreplace(heap, (current_value, iterator))
            #print heap
            break
        else:
            # subseq has been exhausted, therefore remove it from the queue
            heapq.heappop(heap)

#def mergeSingle(sortKey,*subsequences):
def mergeSingle(sortKey, *subsequences):
    # prepare a priority queue whose items are pairs of the form
    # (current-value, iterator), one each per (non-empty) subsequence
    heap = [  ]
    intJudge = {0:str,1:int}
    #print subsequences
    for subseq in subsequences[0]:
        #print subseq
        iterator = iter(subseq)
        for current_value in iterator:
            current_value = current_value.strip()
            current_value = intJudge[current_value.isdigit()](current_value)
            # subseq is not empty, therefore add this subseq's pair
            # (current-value, iterator) to the list
            heap.append((current_value, iterator))
            break
    # make the priority queue into a heap
    heapq.heapify(heap)
    while heap:
        # get and yield lowest current value (and corresponding iterator)
        current_value, iterator = heap[0]
        yield current_value
        for current_value in iterator:
            current_value = current_value.strip()
            current_value = intJudge[current_value.isdigit()](current_value)
            # subseq is not finished, therefore add this subseq's pair
            # (current-value, iterator) back into the priority queue
            #print heap
            heapq.heapreplace(heap, (current_value, iterator))
            #print heap
            break
        else:
            # subseq has been exhausted, therefore remove it from the queue
            heapq.heappop(heap)
